import java.util.Arrays;
import java.util.Stack;

//栈的底层其实是一个顺序表，也就是数组
public class MyStack {
    int[] array;

    int size;

    //构造一个空栈
    public MyStack(){
        array=new int[3];
    }
    //将e压入栈，并返回e
    public int push(int e){
        if(isFull()){
            CapacityExpansion();
        }
        array[size++]=e;
        return e;
    }
    //将栈顶元素出栈，并返回
    public int pop(){
        int e=peek();
        size--;
        return e;
    }
    //获取栈顶元素
    public int peek(){
        if(empty()){
            System.out.println("当前栈为空，无法获取栈顶元素");
        }

        return array[size-1];
    }
    //获取栈中有效的元素个数
    public int size(){

        return size;
    }
    public boolean isFull(){
        return size==array.length;
    }
    //检测栈是否为空
    public boolean empty(){
        return 0==size;
    }
    //扩容
    public void CapacityExpansion(){
        if(size==array.length){
            array= Arrays.copyOf(array,size*2);
        }
    }

    public static void main(String[] args) {
        MyStack array=new MyStack();
        array.push(1);
        array.push(2);
        array.push(3);
        array.push(4);
        array.push(5);
        int x1= array.pop();
        System.out.println(x1);
        x1= array.pop();
        System.out.println(x1);
        x1= array.pop();
        System.out.println(x1);
        x1= array.peek();
        System.out.println(x1);
        System.out.println(array.empty());
    }
    public int evalRPN(String[] tokens) {
        //遍历数组
        int size=tokens.length;
        Stack<Integer> stack=new Stack<>();
        for(String x:tokens){
            //遇到数字入栈
            if(!isOperations(x)){
                stack.push(Integer.parseInt(x));//将字符串转化为一个正数

            }else{
                //遇到运算符出栈两个元素
                //第一个是右操作符，第二个是左操作符
                int num2=stack.pop();
                int num1=stack.pop();
                switch(x){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        } return stack.pop();
    }
    private boolean isOperations(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }
    public boolean isValid(String s) {
        Stack<Character>stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char ch2=stack.peek();
                if(ch2=='['&&ch==']'||ch2=='('&&ch==')'||ch2=='{'&&ch=='}'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if(!stack.empty()){
            return false;
        }return true;
    }
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer>stack=new Stack<>();
        int j=0;
        for(int i=0;i<pushA.length;i++){
            stack.push(pushA[i]);
            while(j<popA.length&&!stack.empty()&&stack.peek()==popA[j]){
                stack.pop();
                j++;
            }

        }
        return stack.empty();
    }
}

